12.34 A tree data structure can store the quad tree. We maintain the bounds of the original region. The tree root represents the original region. Each node is either a leaf that stores an inserted item, or has exactly four children, representing four quadrants. To perform a search, we begin at the root and repeatedly branch to anappropriate quadrant until a leaf (or null entry) is reached. a. Draw the quad tree that corresponds to Figure 12.52. b. What factors influence how deep the (qua d) tree will be? c. Describe an algorithm that performs an orthogonal range query in a quad tree. - | |
| View Solution | |
| << Back | |